// 3357. 最小化相邻元素的最大差值

// int[] nums = [-1, 80, -1, -1, 17];
// s.MinDifference(nums);

public partial class Solution
{
    public int MinDifference(int[] nums)
    {
        var (minL, maxR) = (int.MaxValue, int.MinValue);
        var ans = 0;

        for (int i = 0; i < nums.Length; i++)
            if (nums[i] != -1)
            {
                if ((i - 1 >= 0 && nums[i - 1] == -1) || (i + 1 < nums.Length && nums[i + 1] == -1))
                    (minL, maxR) = (Math.Min(minL, nums[i]), Math.Max(maxR, nums[i]));
                if (!(i - 1 >= 0 && nums[i - 1] == -1))
                    ans = Math.Max(ans, i == 0 ? ans : Math.Abs(nums[i] - nums[i - 1]));
            }

        Func<int, int, int> GetDif1 = (left, right) =>
            Math.Min((maxR - Math.Min(left, right)) / 2 + (maxR - Math.Min(left, right)) % 2,
                    ((Math.Max(left, right) - minL) / 2) + (Math.Max(left, right) - minL) % 2);
        Func<int> GetDif2 = () =>
            (maxR - minL) % 3 == 0 ? (maxR - minL) / 3 : (maxR - minL) / 3 + 1;

        var check = false;
        if (ans == 0)
            ans = int.MinValue;
        else
            check = true;
        var ptr = 0;

        for (int i = 0; i < nums.Length; i++)
            if (nums[i] == -1)
            {
                if (i == nums.Length - 1)
                    ans = Math.Max(ans, GetDif1(nums[ptr], nums[ptr]));
                else
                    for (int j = i + 1; j < nums.Length; j++)
                        if (nums[j] != -1)
                        {
                            if (i == 0)
                                ans = Math.Max(ans, GetDif1(nums[j], nums[j]));
                            else
                                ans = Math.Max(ans, j == i + 1 ? GetDif1(nums[i - 1], nums[j]) : Math.Min(GetDif1(nums[i - 1], nums[j]), GetDif2()));
                            i = j;
                            check = true;
                            break;
                        }
            }
            else
                ptr = i;

        return check ? ans : 0;
    }
}